/*
 * @lc app=leetcode.cn id=327 lang=typescript
 *
 * [327] 区间和的个数
 */

// @lc code=start
function countRangeSum(nums: number[], lower: number, upper: number): number {
  const size = nums.length;

  const prefixSum = new Array(size + 1).fill(0);
  // 计算前缀和
  for (let i = 1; i <= size; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
  }
  // 分治排。排序过程中，先计算左边有多少区间和，在计算右边有多少区间和，合并后递归计算。
  const mergeSort = (
    sum: number[],
    left: number,
    right: number,
    lower: number,
    upper: number
  ): number => {
    if (left >= right) return 0;
    let result = 0;
    let mid = left + ((right - left) >> 1);
    result += mergeSort(sum, left, mid, lower, upper);
    result += mergeSort(sum, mid + 1, right, lower, upper);
    result += countParts(sum, left, mid, mid + 1, right, lower, upper);

    let temp = new Array(right - left + 1);
    let idx = 0;
    let l1 = left;
    let l2 = mid + 1;
    while (l1 <= mid || l2 <= right) {
      if (l2 > right || (l1 <= mid && sum[l1] <= sum[l2])) {
        temp[idx++] = sum[l1++];
      } else {
        temp[idx++] = sum[l2++];
      }
    }
    for (let i = 0; i < temp.length; i++) {
      sum[left + i] = temp[i];
    }
    return result;
  };

  const countParts = (
    sum: number[],
    l1: number,
    r1: number,
    l2: number,
    r2: number,
    lower: number,
    upper: number
  ): number => {
    let result = 0;
    let i = l1;
    let l = l2;
    let r = l2;
    // 计算区间和数量
    while (i <= r1) {
      while (l <= r2 && sum[l] - sum[i] < lower) l++;
      while (r <= r2 && sum[r] - sum[i] <= upper) r++;
      result += r - l;
      i++;
    }
    return result;
  };
  return mergeSort(prefixSum, 0, size, lower, upper);
}
// @lc code=end
